#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// 拓扑排序模版（Leetcode）
// 邻接表建图（动态方式）
// 课程表II
// 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1
// 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi]
// 表示在选修课程 ai 前 必须 先选修 bi
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1]
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序
// 你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组
// 测试链接 : https://leetcode.cn/problems/course-schedule-ii/

// 加餐！！！
// 207. 课程表 : https://leetcode.cn/problems/course-schedule/description/
// 1462. 课程表 IV : https://leetcode.cn/problems/course-schedule-iv/description/
// 207. 课程表的代码和本道题是类似的，将本道题的代码改一下就能过
// 1462. 课程表 IV 是根据拓扑排序结果回答询问的题目，相关的代码，我已经贴到文件的最后了

// 数组实现的队列
class Solution 
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 0 ~ n - 1
        vector<vector<int>> g(numCourses);
        // 入度表
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            // x -> y
            int x = e[1], y = e[0];
            g[x].push_back(y);
            ++inDeg[y];
        }

        vector<int> ret;
        int q[numCourses], l = 0, r = 0;
        memset(q, 0, sizeof(q));
        for(int i = 0; i < numCourses; ++i)
        {
            if(inDeg[i] == 0) q[r++] = i;
        }

        while(l < r)
        {
            int x = q[l++];
            ret.push_back(x);
            for(int y : g[x])
            {
                if(--inDeg[y] == 0) q[r++] = y;
            }
        }

        if(ret.size() == numCourses) return ret;
        return {};
    }
};

// 使用标准库中的队列
class Solution 
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 0 ~ n - 1
        vector<vector<int>> g(numCourses);
        // 入度表
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            // x -> y
            int x = e[1], y = e[0];
            g[x].push_back(y);
            ++inDeg[y];
        }

        vector<int> ret;
        queue<int> q;
        for(int i = 0; i < numCourses; ++i)
        {
            if(inDeg[i] == 0) q.push(i);
        }

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            ret.push_back(x);
            for(int y : g[x])
            {
                if(--inDeg[y] == 0) q.push(y);
            }
        }

        if(ret.size() == numCourses) return ret;
        return {};
    }
};

// 1462. 课程表 IV : https://leetcode.cn/problems/course-schedule-iv/description/
class Solution 
{
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) 
    {
        vector<vector<int>> g(numCourses);
        vector<int> inDeg(numCourses);
        for(auto& e : prerequisites)
        {
            // x -> y
            int x = e[0], y = e[1];
            g[x].push_back(y);
            ++inDeg[y];
        }

        queue<int> q;
        for(int i = 0; i < numCourses; ++i) if(!inDeg[i]) q.push(i);

        vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses));
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            for(int y : g[x])
            {
                isPre[x][y] = true; // x 是 y 的先修课程
                // 由于 x 是 y 的先修课程，那么就看一下 i 是否是 x 的先修课程
                //  如果是， 那么 i 也是 y 的先修课程
                // 由于 isPre[i][y] 有可能已经是 true 了，所以需要按位或上 isPre[i][y]
                for(int i = 0; i < numCourses; ++i)
                {
                    isPre[i][y] = isPre[i][y] | isPre[i][x]; 
                }

                if(--inDeg[y] == 0) q.push(y);
            }
        }

        vector<bool> ret;
        // 回答询问
        for(auto& q : queries)
        {
            // x 是否是 y 的先修课程
            int x = q[0], y = q[1];
            ret.push_back(isPre[x][y]);
        }
        return ret;
    }
};